/* Universidad del Valle de Guatemala
 * CC2003 - Algoritmos y Estructuras de Datos
 * HOJA DE TRABAJO #7
 * Fecha de Entrega: Sábado 8 de Octubre de 2011
 */

/**
 * Clase que permite la implementación de la interfaz PriorityQueue por medio
 * de un vector.
 * @author José Antonio Bagur - 10275
 */

// SE IMPORTAN LOS PAQUETES A UTILIZAR EN LA CLASE
import java.util.*;

public class PriorityVector <E> implements PriorityQueue <E> {
    
        /* ATRIBUTOS DE LA CLASE PRIORITY VECTOR */
    
        protected Vector <E> data;
        
        /* MÉTODOS DE LA CLASE PRIORITY VECTOR */
        
        /**
         * Constructor de la clase PriorityVector, inicializa el estado de la 
         * cola.
         */
        public PriorityVector() {
            data = new Vector<E>();
        }
        
        
        /**
         * Método que permite obtener el valor mínimo de la cola.
         * @return valor E mínimo de la cola.
         */
        public E getFirst() {
            return data.get(0);
        }
        
        
        /**
         * Método que remueve y regresa el valor mínimo de la cola.
         * @return valor E mínimo de la cola.
         */
        public E remove() {
            return data.remove(0);
        }
        
        
        /**
         * Método que permite añadir un valor a la cola y dejarla en orden.
         * @param value 
         */
        public void add(E value) {
            int position = locate(value);
            data.add(position,value);
        }
        
        
        /**
         * Método que permite ordenar los elementos de la cola.
         * @param target
         * @return locación del valor.
         */
        protected int locate(E target) {
            Comparable<E> midValue;
            int low = 0;
            int high = data.size();
            int mid = (low + high)/2;
            while (low < high) {
                midValue = (Comparable<E>) data.get(mid);
                if (midValue.compareTo(target)<0) {
                    low = mid + 1;
                } else {
                    high = mid;
                } 
                mid = (low + high)/2;
            }
            
            return low;        
        }
        
        
        /**
         * Método que permite conocer el tamaño de la cola.
         * @return tamaño int de la cola.
         */
        public int size() {
            return data.size();
        }
        
        
        /**
         * Método que permite conocer si la cola se encuentra vacía. 
         * @return true si la cola se encuentra vacía.
         */
        public boolean isEmpty() {
            return data.size() == 0;
        }
        
        
        @Override
        public int compareTo(E o) { 
            throw new UnsupportedOperationException("Not supported yet.");
        }
                
}
